package com.leetcode.partition5;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/12 14:47
 */
public class LC473火柴拼正方形 {

    public static boolean makesquare(int[] matchsticks) {
        Arrays.sort(matchsticks);
        int sum = 0;
        for (int i = 0; i < matchsticks.length; i++) sum += matchsticks[i];
        if (sum % 4 != 0) return false;
        return backtracking(new int[4], sum >> 2, matchsticks.length - 1, matchsticks);
    }

    public static void main(String[] args) {
        int[] matchsticks = {3, 3, 3, 3, 4};
        System.out.println(makesquare(matchsticks));
    }

    private static boolean backtracking(final int[] bucket, int capacity, int stickIndex, final int[] matchsticks) {
        if (stickIndex < 0) return true;               //火柴从后往前遍历，如果stickIndex小于0，说明所有的桶都能刚刚装满
        for (int i = 0; i < bucket.length; i++) {
            //如果当前桶刚刚装满或者放下当前火柴后还有空间继续放
            if ((bucket[i] + matchsticks[stickIndex] == capacity) || (bucket[i] + matchsticks[stickIndex] < capacity)) {
                bucket[i] += matchsticks[stickIndex];           //放入当前桶
                if (backtracking(bucket, capacity, stickIndex - 1, matchsticks)) return true;       //当前放法能够满足条件，不需要回溯
                bucket[i] -= matchsticks[stickIndex];           //当前放入方法不能刚好放满所有桶，回溯
            }
        }
        return false;
    }
}
